package question.solution45;

import question.SolutionTemplate;

public class Solution45 implements SolutionTemplate {

    public int jump(int[] nums) {
        int jumpTimes = 0;
        int currentStage = 0;
        while(currentStage < nums.length-1){
            int maxPossibleCapableDistance = 0;
            int maxPossibleCurrentStage = currentStage;
            int currentCapableDistance = nums[currentStage];

            for(int i=currentStage + currentCapableDistance;i>currentStage;i--){
                if(i >= nums.length-1){
                    maxPossibleCurrentStage = i;
                    break;
                }
                int possibleCapableDistance = i - currentStage + nums[i];
                if(possibleCapableDistance > maxPossibleCapableDistance){
                    maxPossibleCapableDistance = possibleCapableDistance;
                    maxPossibleCurrentStage = i;
                }
            }
            currentStage = maxPossibleCurrentStage;
            jumpTimes++;
        }
        return jumpTimes;
    }


    public void test() {
        int[] nums = {2,3,1,1,4};
        int result = jump(nums);
        return;
    }
}
